When a computer software application initiates an operation to update the data in a quorum-based data replication system, such as a system that uses Paxos protocols where multiple replicas of data are stored on one or more data storage devices, completion of the data update is reported to the application when acceptance of the data update is reported by a majority of the data replicas. In many types of applications, some types of these operations are of short duration, and may require few computational resources, but are important to complete quickly, whereas other types of operations that involve read-only transactions that are of longer duration and/or are more computationally resource-intensive are less important to complete quickly. Supporting such operations in a quorum-based data replication system using conventional techniques often leads to situations where short, simple data operations are blocked while long, complex data operations are being performed. This is especially undesirable where the short, simple data operations are high-priority write operations.